package org.lan.interview.mock;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author <p><a href="mailto:1728209643@qq.com">XiaoSan</a>
 * @date 2019/11/21 4:02 PM
 */
public class Mock_003 {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> iLists = new ArrayList<>();
        int n = intervals.length;
        if (n == 0) {
            iLists.add(newInterval);
            return iLists.toArray(new int[0][]);
        }
        int i;
        for (i = 0; i < n; i++) {
            if (intervals[i][1] >= newInterval[0]) {
                break;
            }
            iLists.add(intervals[i]);
        }
        if (i == n) {
            iLists.add(newInterval);
            return iLists.toArray(new int[0][]);
        }

        if (intervals[i][0] > newInterval[1]) {
            iLists.add(newInterval);
        } else {
            int head = Math.min(newInterval[0], intervals[i][0]), tail = Math.max(newInterval[1], intervals[i][1]);
            i++;
            while (i < n && intervals[i][0] <= tail) {
                tail = Math.max(newInterval[1], intervals[i][1]);
                i++;
            }
            iLists.add(new int[]{head, tail});
        }
        while (i < n) {
            iLists.add(intervals[i++]);
        }
        return iLists.toArray(new int[0][]);
    }


    public static void main(String[] args) {
        int[][] intervals = {{1, 5}};
        System.out.println(Arrays.deepToString(new Mock_003().insert(intervals, new int[]{6, 8})));
    }
}
